「AHOI2017/HNOI2017」大佬

发表于 | 分类于 | | 浏览量： 次

这题面，生动形象，饶有趣味，interesting！出题人呢？

传送门

洛谷P3724

BZOJ4828

题解

先把又臭又长的题面读两遍，然后很显然，保证自己不死和把大佬怼死是两个不同的环节，两个问题，分别解决，互不干扰（这话咋这么耳熟呢）。

设$F[i][j]​$表示到了第$i​$天，自己的自信值为$j​$，最多可以多少天不刷水题。

那么就可以腾出$\max{i=1}^{n}{\max{j=0}^{mc}{F[i][j]}}​$天来专门怼大佬。

注意不是$\max_{j=0}^{mc}{F[n][j]}​$，可能还没到第$n​$天就可以把大佬怼死，但是到了第$n​$天不可能不被大佬怼死。

那么问题就转化为：给你$D​$天，每天可以执行操作1、3、4或5，问你能不能把大佬的自信值怼到$0​$？

注意是怼到$0​$，不能单纯刷DP取最大值，那样可能把大佬的自信值怼到负，而且可以怼的自信值不一定连续。

设一种只用操作3、4、5的怼大佬方案为$(Hurt，Day)​$表示用了$Day​$天对大佬产生了$Hurt​$点伤害，发现数据范围并不大，所以就可以用BFS把所有方案都列出来。至于到底有多少种方案，玄学，反正数组开大点就好了。$Hash​$判重，直接调STL里的map的话时效会差一些。（但是我懒，所以调了map）

然后把所有怼大佬的方案按照伤害排序，用两个指针，一头一尾扫过去就好了，注意两个方案的伤害之和不能超过大佬的自信值，且剩下位怼完的自信值可以用剩余的天数通过操作1把大佬怼死就行了。

代码

稍微有点长QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=105,inf=0x3F3F3F3F;
int n,m,mc,a[maxn],w[maxn],D,F[maxn][maxn],tot,T[2000005];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void GetFightDays()            //刷DP计算天数
{
	memset(F,-1,sizeof(F));F[0][mc]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i];j<=mc;j++)       //注意不要越界
		{
			F[i][j-a[i]]=max(F[i][j-a[i]],F[i-1][j]+1);
			int x=min(mc,j-a[i]+w[i] );
			F[i][x]=max(F[i][x],F[i-1][j]);
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=mc;j++)
			if(F[i][j]>D)
				D=F[i][j];
}
struct Node{int F,L;}Q[2000005];
map<int,map<int,int> > Day;
struct Plan
{
	int Hurt,Days;
	bool operator < (const Plan& b)const{return Hurt<b.Hurt;}
}P[2000005];
inline void BFS()
{
	int hed=0,til=1,ddd;
	Q[1]=(Node){1,0};Day[1][0]=T[1]=1;//刷BFS搞出所有可能的方案
	while(hed!=til)
	{
		hed++;ddd=Day[Q[hed].F][Q[hed].L];
		if(ddd>=D) continue;
		if(!Day[Q[hed].F][Q[hed].L+1])
		{
			til++;Q[til].F=Q[hed].F;Q[til].L=Q[hed].L+1;
			Day[Q[til].F][Q[til].L]=T[til]=ddd+1;
		}
		if((LL)Q[hed].F*Q[hed].L<=100000000&&!Day[Q[hed].F*Q[hed].L][Q[hed].L])
		{
			til++;Q[til].F=Q[hed].F*Q[hed].L;Q[til].L=Q[hed].L;
			Day[Q[til].F][Q[til].L]=T[til]=ddd+1;
		}
	}
	P[++tot]=(Plan){0,0};
	for(int i=1;i<=til;i++)
		P[++tot]=(Plan){Q[i].F,Day[Q[i].F][Q[i].L]};
	sort(P+1,P+1+tot);
}
int Check(int C)
{
	int j=1,mi=inf;
	for(int i=tot;i;i--)
	{
		while(i>j&&P[i].Hurt+P[j].Hurt<=C)
		{
			mi=min(mi,P[j].Days-P[j].Hurt);
			j++;
		}
		if(D>=C-P[i].Hurt+P[i].Days+mi) return 1;
	}
	return 0;
}
int main()
{
	n=read();m=read();mc=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) w[i]=read();
	GetFightDays();
	BFS();
	while(m--)
	{
		int Ci=read();
		printf("%d\n",Check(Ci));
	}
	return 0;
}